﻿/*
题目：网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

https://leetcode.cn/problems/network-delay-time/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& edges, int n, int s) {
        vector<vector<int>> G(n + 1, vector<int>(n + 1, INT_MAX));
        for (const auto& edge : edges)
            G[edge[0]][edge[1]] = edge[2];

        vector<int> d(n + 1, INT_MAX);      // 最短路径数组
        vector<bool> vis(n + 1, false);     // 是否访问过（是否更新了最短路径）
        d[s] = 0;

        for (int i = 1; i <= n; i++) {
            int u = -1;
            int min = INT_MAX;
            for (int j = 1; j <= n; j++) {
                if (d[j] < min && vis[j] == false) {
                    u = j;
                    min = d[j];
                }
            }

            if (u == -1)    break;      // 已经不存在没访问的最短路径了
            vis[u] = true;

            // 更新所有最短路径
            for (int v = 1; v <= n; v++) {
                if (vis[v] == false && G[u][v] != INT_MAX && d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                }
            }
        }

        int res = *max_element(d.begin() + 1, d.end());
        return res == INT_MAX ? -1 : res;
    }
};